// https://www.lincode.com/problem/minimum-window-substring/

class Solution {
public:
    /**
     * @param source : A string
     * @param target: A string
     * @return: A string denote the minimum window, return "" if there is no such a string
     */
    string minWindow(string &source , string &target) {
        map<char, int> record;
        string result;
        for (int i = 0; i < target.size(); ++i)
        {
            record[target[i]]++;
        }
        int cnt = 0;
        int s = record.size(); //record的size是变化的，一开始要记住！！！
        int j = 0;
        int min = INT_MAX;
        for (int i = 0; i < source.size(); ++i)
        {
            while (j < source.size() && cnt != s)
            {
                record[source[j]]--;
                if (record[source[j++]] == 0) cnt++;
                if (cnt == s) break;
            }
            if (cnt == s && j - i < min)
            {
                min = j - i;
                result = source.substr(i, j - i);
            }
            if (record[source[i]] == 0) cnt--;
            record[source[i]]++;
        }
        return result;
    }
};